#!usr/bin/env python  
# -*- coding:utf-8 _*-
""" 
@author:robot
@file: quicksort.py 
@version:
@time: 2023/03/29 
"""


def main(nums):
    low = 0
    high = len(nums) - 1
    return quick_sort(nums, low, high)


def quick_sort(nums, low, high):
    if low >= high: return
    i = low
    j = high
    key = nums[i]
    while i < j:
        while i < j and key <= nums[j]:
            j -= 1
        # 到这里nums[j]已经小于key了
        # 所以nums[i]被赋值为nums[j]
        nums[i] = nums[j]
        while i < j and key >= nums[i]:
            i += 1
        # 到这里nums[i]已经大于key了
        # 所有nums[j]被赋值为nums[i]
        nums[j] = nums[i]
    # 将key放到nums[i]的位置
    nums[i] = key
    quick_sort(nums, low, i - 1)
    quick_sort(nums, i + 1, high)
    return nums


def quick_sort2(nums, low, high):
    if low >= high: return
    i = low
    j = high
    key = nums[i]
    while i < j:
        while i < j and key <= nums[j]:
            j -= 1
        nums[i] = nums[j]
        while j < i and key >= nums[i]:
            i -= 1
        nums[j] = nums[i]
    nums[i] = key
    quick_sort2(nums, low, i - 1)
    quick_sort2(nums, i + 1, high)
    return nums


print(main([1, 2, 3, 4, 7, 6, 5]))
